package com.example.recur;

/**
 * @Date 2023-07-02
 * @Author Jonathan
 * </p>
 * 1.大问题拆成两个子问题
 * 2.子问题求解的方式和求解大问题一样
 * 3.存在结果已知的最小子问题
 * <p/>
 * 先序遍历
 * 中序遍历
 * 后序遍历
 */
public class Tree {


    private void preOrder(TreeNode root) {
        // 最小子问题
        if (root == null) {
            return;
        }
        // 遍历打印根节点
        System.out.println(root.value);
        // 遍历左子树
        preOrder(root.left);
        // 遍历右子树
        preOrder(root.right);
    }

    private void inOrder(TreeNode root) {
        // 最小子问题
        if (root == null) {
            return;
        }
        // 遍历左子树
        inOrder(root.left);
        // 遍历打印根节点
        System.out.println(root.value);
        // 遍历右子树
        inOrder(root.right);
    }

    private Integer maxDepth(TreeNode root) {
        return process(root).depth;

    }

    private Info process(TreeNode root) {
        if (root == null) {
            return new Info(0);
        }
        Info left = process(root.left);
        Info right = process(root.right);
        // 后续遍历  从左边右边抓取值
        Integer maxDepth = Math.max(left.depth, right.depth) + 1;
        return new Info(maxDepth);
    }

    static class Info {
        private final Integer depth;

        public Info(Integer depth) {
            this.depth = depth;
        }
    }

}
